package DMSXL._2024.BinaryTrees;

import java.lang.reflect.AnnotatedArrayType;
import java.util.ArrayList;
import java.util.List;

public class binaryTreePaths {
    public static void main(String[] args) {
        Integer[] nums = {1,2,3,null,5};
        TreeNode root = CreateTree.createBinaryTree(nums,0);
        System.out.println(new binaryTreePaths().binaryTreePaths(root));
    }
    List<String> result = new ArrayList<>();
    String path = "";
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return result;
        }
        backTracking(root);
        return result;
    }
    public void backTracking(TreeNode root){
        //如果为空啥都不做
        if(root == null){
            return;
        }
        //如果路径为空，只需要加入数字即可
        if(path.isEmpty()){
            path += root.val;
        }
        //路径不为空需要加入占位符，
        else {
            path += "," + root.val;
        }

        if(root.left == null && root.right == null){
            String temp = "";
            for (int i = 0; i < path.length(); i++) {
                if(path.charAt(i) == ','){
                    temp += "->";
                }else {
                    temp += path.charAt(i);
                }

            }
            result.add(temp);
            return;
        }

        if(root.left != null){
            backTracking(root.left);
            if(path.length() == Integer.toString(root.val).length()){
                path = path.substring(0,path.length() - Integer.toString(root.left.val).length());
            }else {
                path = path.substring(0,path.length() - Integer.toString(root.left.val).length() - 1);
            }

        }
        if(root.right != null){
            backTracking(root.right);
            if(path.length() == Integer.toString(root.val).length()){
                path = path.substring(0,path.length() - Integer.toString(root.right.val).length());
            }else {
                path = path.substring(0,path.length() - Integer.toString(root.right.val).length() - 1);
            }
        }
    }
}
